package 中等.搜索.回溯;

/**
 * 给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 
 * 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。
 * 注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
 * 返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/largest-sum-of-averages
 */
public class 最大平均值和的分组_813 {

    public static void main(String[] args) {

        System.out.println(new 最大平均值和的分组_813().largestSumOfAverages(new int[]{4663, 3020, 7789, 1627, 9668,
                1356, 4207, 1133, 8765, 4649, 205, 6455, 8864, 3554, 3916, 5925, 3995, 4540, 3487, 5444, 8259, 8802, 6777, 7306, 989,
                4958, 2921, 8155, 4922, 2469, 6923, 776, 9777, 1796, 708, 786, 3158, 7369, 8715, 2136, 2510, 3739, 6411, 7996,
                6211, 8282, 4805, 236, 1489, 7698
        }, 27));

    }

    private double maxAverage = 0;

    private int k_;

    /**
     * 回溯+剪枝（超时）
     *
     * @param nums
     * @param k
     * @return
     */
    public double largestSumOfAverages(int[] nums, int k) {
        k_ = k;
        double sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            dfs(i + 1, nums, 1, sum / (i + 1));
        }

        return maxAverage;
    }

    private void dfs(int left, int[] nums, int curK, double curAverage) {
        if (curK + nums.length - left < k_) {
            return;
        }
        if (curK > k_) {
            return;
        }
        if (curK == k_ && left == nums.length) {
            maxAverage = Math.max(maxAverage, curAverage);
            return;
        }
        double sum = 0;
        for (int i = left; i < nums.length; i++) {
            sum += nums[i];
            dfs(i + 1, nums, curK + 1, curAverage + sum / (i - left + 1));
        }
    }

}
